package name.huzhenbo.java.algorithm.tree;

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.lang.reflect.Array;

/**
 * heap:
 * insert: O(logn)
 * extractMin: 0(logn)
 * n times insert/extractMin: O(nlogn)
 *
 * sorted array:
 * insert: O(n)
 * extractMin: O(1)
 * n times insert/extractMin: O(n2)
 *
 * unsorted array:
 * insert: O(1)
 * extractMin: O(n)
 * times insert/extractMin: O(n2)
 */
class Heap<T extends Comparable<? super T>> {
    private List<T> heap;

    public Heap() {
        heap = new ArrayList<T>();
        heap.add(null);
    }

    public int push(T value) {
        heap.add(value);
        return shiftup();
    }

    public int replaceFirst(T value) {
        heap.set(1, value);
        return shiftdown();
    }

    /**
     * heap[i] >= heap[i/2]
     * <p/>
     * here i is one started index
     */
    private int shiftup() {
        int heapIndex = size();
        while (heapIndex > 1) {
            int parentHeapIndex = heapIndex / 2;
            if (val(heapIndex).compareTo(val(parentHeapIndex)) < 0) {
                swap(heapIndex, parentHeapIndex);
                heapIndex = parentHeapIndex;
            } else {
                break;
            }
        }
        return heapIndex;
    }

    private int shiftdown() {
        int current = 1;
        int nextPos = current * 2;
        while (nextPos <= size()) {
            if(nextPos + 1 <= size()){
                nextPos = val(nextPos + 1).compareTo(val(nextPos)) > 0 ? nextPos : nextPos + 1;
            }
            if(val(nextPos).compareTo(val(current)) >= 0){
                break;
            }
            swap(current, nextPos);
            current = nextPos;
            nextPos = current * 2;
        }
        return current;
    }

    public T[] toArray(Class<T> clazz) {
        return Arrays.copyOfRange(heap.toArray((T[])Array.newInstance(clazz, 0)), 1, heap.size());
    }

    public int size() {
        return heap.size() - 1;
    }

    private T val(int index) {
        return heap.get(index);
    }

    private void swap(int indexI, int indexJ) {
        T temp = heap.get(indexI);
        heap.set(indexI, heap.get(indexJ));
        heap.set(indexJ, temp);
    }

    public T extractMin() {
        if(size() == 0){
            return null;
        }
        T result = val(1);
        heap.set(1, heap.get(size()));
        heap.remove(size());
        shiftdown();
        return result;
    }
}
